package com.dyz.leetcode._20_dynamicProgramming;

public class _64_minPathSum {
    // 使用回溯
    private int[][] dirs = {{1,0}, {0, 1}};
    private int minPathSum = Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        dfs(grid, 0, 0, grid[0][0]);
        return minPathSum;
    }

    private void dfs(int[][] grid, int row, int col, int sum) {
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            minPathSum = Math.min(minPathSum, sum);
            return;
        }

        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            if (nextRow < 0 || nextCol < 0
                    || nextRow >= grid.length
                    || nextCol >= grid[0].length) {continue;}
            sum += grid[nextRow][nextCol];
            dfs(grid, nextRow, nextCol, sum);
            sum -= grid[nextRow][nextCol];
        }
    }



    public int minPathSum1(int[][] grid) {
        return dfs1(grid, 0, 0);

    }

    private int dfs1(int[][] grid, int row, int col) {
        if(row==grid.length-1  && col==grid[0].length-1){
            return grid[row][col];
        }

        int minPathSum = Integer.MIN_VALUE;
        for(int[] dir:dirs){
            int nextRow = row+dir[0];
            int nextCol = col+dir[1];
            if(nextRow<0 || nextCol<0 || nextRow>grid.length|| nextCol>grid[0].length){continue;}
            int childMinPathSum = dfs1(grid, nextRow, nextCol);
            minPathSum = Math.min(minPathSum, childMinPathSum);
        }

        return minPathSum+grid[row][col];
    }


    //动态规划
    public int minPathSum2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //状态定义：dp[i][j] 表示从坐标（i，j）到右下角的最短路径和
        int [][] dp = new int[m][n];
        //状态初始化
        dp[m-1][n-1] = grid[m-1][n-1];

        //状态转移
        for (int i = m-1; i >=0; i--) {
            for (int j = n-1; j >=0; j--) {
                if(i==m-1&&j!=n-1){
                    dp[i][j] = grid[i][j]+dp[i][j+1];
                }else if(i!=m-1&&j==n-1){
                    dp[i][j] = grid[i][j]+dp[i+1][j];
                }else if(i!=m-1 && j!=n-1){
                    dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) +grid[i][j];
                }
            }
        }
        return dp[0][0];
    }

    //动态规划+空间压缩
    public int minPathSum3(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //状态定义：dp[i][j] 表示从坐标（i，j）到右下角的最短路径和
        int [] dp = new int[n]; //以行为单位
        //状态初始化
        dp[n-1] = grid[m-1][n-1];

        //状态转移
        for (int i = m-1; i >=0; i--) {
            for (int j = n-1; j >=0; j--) {
                if(i==m-1&&j!=n-1){
                    dp[j] = grid[i][j]+dp[j+1];
                }else if(i!=m-1&&j==n-1){
                    dp[j] = grid[i][j]+dp[j];
                }else if(i!=m-1 && j!=n-1){
                    dp[j] = Math.min(dp[j+1], dp[j]) +grid[i][j];
                }
            }
        }
        return dp[0];

    }



}
